/**
 * 腐烂的苹果
 *
 * 描述
 * 给定一个  n×m  的网格，其中每个单元格中可能有三种值中的一个 0 , 1 , 2。
 * 其中 0 表示这个格子为空、1 表示这个格子有一个完好的苹果，2 表示这个格子有一个腐烂的苹果。
 * 腐烂的苹果每分钟会向上下左右四个方向的苹果传播一次病菌，并导致相邻的苹果腐烂。请问经过多少分钟
 * ，网格中不存在完好的苹果。如果有苹果永远不会腐烂则返回 -1。
 *
 * 数据范围： 1≤n,m≤1000  ，网格中的值满足 0≤val≤2
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 这里我们用多源深搜, 首先将所有的 2 加入队列,
 * 然后每一次循环处理上一次加入队列的位置, 要是, 后面没有加入
 * 了, 就说明毒苹果已经感染完毕, 最后面只需要在判断一次就可以了
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n ^ 2)
 */
public class Main {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型ArrayList<ArrayList<>>
     * @return int整型
     */
    public int rotApple (ArrayList<ArrayList<Integer>> grid) {

        int m = grid.size(), n = grid.get(0).size();

        // 是否感染过
        boolean[][] vis = new boolean[m][n];

        // 深搜队列
        Queue<int[]> q = new LinkedList<>();

        // 第一次循环将所有的 坏苹果加入队列
        for (int i = 0; i < m; i++) {
            for (int j = 0 ;j < n; j++) {
                if (grid.get(i).get(j) == 2) {
                    q.add(new int[]{i, j});
                }
            }
        }

        // 这里记录用了多少分钟
        int ret = 0;

        // 开始深搜
        while (!q.isEmpty()) {

            // 这里每一次深搜都是一分钟
            ret++;

            // 这里只处理上一次队里里面的位置, 所以先将大小读取出来
            // 正好利用先进先出
            int sz = q.size();

            // 处理
            for (int i = 0; i < sz; i++) {

                int[] arr = q.poll();

                for (int k = 0; k < 4; k++) {

                    // 向四周深搜
                    int a = dx[k] + arr[0],
                            b = dy[k] + arr[1];

                    // 条件判断
                    if (a >= 0 && a < m
                            && b >= 0 && b < n
                            && grid.get(a).get(b) == 1
                            && !vis[a][b]) {

                        // 没有感染过且是 1, 成功感染
                        q.add(new int[]{a, b});

                        // 更新
                        vis[a][b] = true;
                    }
                }
            }
        }

        // 最后一次循环判断是否还有没有感染过的苹果
        for (int i = 0; i < m; i++) {
            for (int j = 0 ;j < n; j++) {

                // 这里要同时满足两个条件
                // 是 1, 且感染记录中没有他
                if (grid.get(i).get(j) == 1
                        && !vis[i][j]) {

                    // 有好苹果 返回 -1
                    return -1;
                }
            }
        }

        // 这里要 -1, 因为最后面队列中是还有值的, 他还会再循环一次, 就会在经历一分钟
        return ret - 1;
    }
}